/* Copyright (c) 2020 XEPIC Corporation Limited */
/*
 * Copyright (c) 1998-2018 Stephen Williams (steve@icarus.com)
 *
 *    This source code is free software; you can redistribute it
 *    and/or modify it in source code form under the terms of the GNU
 *    General Public License as published by the Free Software
 *    Foundation; either version 2 of the License, or (at your option)
 *    any later version.
 *
 *    This program is distributed in the hope that it will be useful,
 *    but WITHOUT ANY WARRANTY; without even the implied warranty of
 *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *    GNU General Public License for more details.
 *
 *    You should have received a copy of the GNU General Public License
 *    along with this program; if not, write to the Free Software
 *    Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
 * USA.
 */

#include "verinum.h"

#include <algorithm>
#include <cassert>
#include <climits>
#include <cmath>   // Needed to get pow for as_double().
#include <cstdio>  // Needed to get snprintf for as_string().
#include <iostream>

#include "config.h"

#if !defined(HAVE_LROUND)
/*
 * If the system doesn't provide the lround function, then we provide
 * it ourselves here. It is simply the nearest integer, rounded away
 * from zero.
 */
extern "C" long int lround(double x) {
  if (x >= 0.0)
    return (long)floor(x + 0.5);
  else
    return (long)ceil(x - 0.5);
}
#endif

static verinum::V add_with_carry(verinum::V l, verinum::V r, verinum::V& c);

verinum::verinum()
    : bits_(0),
      nbits_(0),
      has_len_(false),
      has_sign_(false),
      is_single_(false),
      string_flag_(false) {}

verinum::verinum(const V* bits, unsigned nbits, bool has_len__)
    : has_len_(has_len__),
      has_sign_(false),
      is_single_(false),
      string_flag_(false) {
  nbits_ = nbits;
  bits_ = new V[nbits];
  for (unsigned idx = 0; idx < nbits; idx += 1) {
    bits_[idx] = bits[idx];
  }
}

static string process_verilog_string_quotes(const string& str) {
  string res;

  int idx = 0;
  int str_len = str.length();

  while (idx < str_len) {
    if (str[idx] == '\\') {
      idx += 1;
      assert(idx < str_len);
      switch (str[idx]) {
        case 'n':
          res = res + '\n';
          idx += 1;
          break;
        case 't':
          res = res + '\t';
          idx += 1;
          break;
        case '0':
        case '1':
        case '2':
        case '3':
        case '4':
        case '5':
        case '6':
        case '7': {
          char byte_val = 0;
          int odx = 0;
          while (odx < 3 && idx + odx < str_len && str[idx + odx] >= '0' &&
                 str[idx + odx] <= '7') {
            byte_val = 8 * byte_val + str[idx + odx] - '0';
            odx += 1;
          }
          idx += odx;
          res = res + byte_val;
          break;
        }
        default:
          res = res + str[idx];
          idx += 1;
          break;
      }
    } else {
      res = res + str[idx];
      idx += 1;
    }
  }
  return res;
}

verinum::verinum(const string& s)
    : has_len_(true), has_sign_(false), is_single_(false), string_flag_(true) {
  string str = process_verilog_string_quotes(s);
  nbits_ = str.length() * 8;

  // Special case: The string "" is 8 bits of 0.
  if (nbits_ == 0) {
    nbits_ = 8;
    bits_ = new V[nbits_];
    bits_[0] = V0;
    bits_[1] = V0;
    bits_[2] = V0;
    bits_[3] = V0;
    bits_[4] = V0;
    bits_[5] = V0;
    bits_[6] = V0;
    bits_[7] = V0;
    return;
  }

  bits_ = new V[nbits_];

  unsigned idx, cp;
  V* bp = bits_ + nbits_;
  for (idx = nbits_, cp = 0; idx > 0; idx -= 8, cp += 1) {
    char ch = str[cp];
    *(--bp) = (ch & 0x80) ? V1 : V0;
    *(--bp) = (ch & 0x40) ? V1 : V0;
    *(--bp) = (ch & 0x20) ? V1 : V0;
    *(--bp) = (ch & 0x10) ? V1 : V0;
    *(--bp) = (ch & 0x08) ? V1 : V0;
    *(--bp) = (ch & 0x04) ? V1 : V0;
    *(--bp) = (ch & 0x02) ? V1 : V0;
    *(--bp) = (ch & 0x01) ? V1 : V0;
  }
}

verinum::verinum(verinum::V val, unsigned n, bool h)
    : has_len_(h), has_sign_(false), is_single_(false), string_flag_(false) {
  nbits_ = n;
  bits_ = new V[nbits_];
  for (unsigned idx = 0; idx < nbits_; idx += 1) bits_[idx] = val;
}

verinum::verinum(uint64_t val, unsigned n)
    : has_len_(true), has_sign_(false), is_single_(false), string_flag_(false) {
  nbits_ = n;
  bits_ = new V[nbits_];
  for (unsigned idx = 0; idx < nbits_; idx += 1) {
    bits_[idx] = (val & 1) ? V1 : V0;
    val >>= (uint64_t)1;
  }
}

/* The second argument is not used! It is there to make this
 * constructor unique. */
verinum::verinum(double val, bool)
    : has_len_(false), has_sign_(true), is_single_(false), string_flag_(false) {
  bool is_neg = false;
  double fraction;
  int exponent;
  const unsigned BITS_IN_LONG = 8 * sizeof(long);

  /* We return `bx for a NaN or +/- infinity. */
  if (val != val || (val && (val == 0.5 * val))) {
    nbits_ = 1;
    bits_ = new V[nbits_];
    bits_[0] = Vx;
    return;
  }

  /* Convert to a positive result. */
  if (val < 0.0) {
    is_neg = true;
    val = -val;
  }

  /* Round to the nearest integer now, as this may increase the
     number of bits we need to allocate. */
  val = round(val);

  /* Get the exponent and fractional part of the number. */
  fraction = frexp(val, &exponent);
  nbits_ = exponent + 1;
  bits_ = new V[nbits_];

  /* If the value is small enough just use lround(). */
  if (nbits_ <= BITS_IN_LONG) {
    long sval = lround(val);
    if (is_neg) sval = -sval;
    for (unsigned idx = 0; idx < nbits_; idx += 1) {
      bits_[idx] = (sval & 1) ? V1 : V0;
      sval >>= 1;
    }
    /* Trim the result. */
    signed_trim();
    return;
  }

  unsigned nwords = (exponent - 1) / BITS_IN_LONG;

  fraction = ldexp(fraction, (exponent - 1) % BITS_IN_LONG + 1);

  if (nwords == 0) {
    unsigned long bits = (unsigned long)fraction;
    fraction = fraction - (double)bits;
    for (unsigned idx = 0; idx < nbits_; idx += 1) {
      bits_[idx] = (bits & 1) ? V1 : V0;
      bits >>= 1;
    }
  } else {
    for (int wd = nwords; wd >= 0; wd -= 1) {
      unsigned long bits = (unsigned long)fraction;
      fraction = fraction - (double)bits;
      unsigned max_idx = (wd + 1) * BITS_IN_LONG;
      if (max_idx > nbits_) max_idx = nbits_;
      for (unsigned idx = wd * BITS_IN_LONG; idx < max_idx; idx += 1) {
        bits_[idx] = (bits & 1) ? V1 : V0;
        bits >>= 1;
      }
      fraction = ldexp(fraction, BITS_IN_LONG);
    }
  }

  /* Convert a negative number if needed. */
  if (is_neg) {
    *this = -(*this);
  }

  /* Trim the result. */
  signed_trim();
}

/* This is used by the double constructor above. It is needed to remove
 * extra sign bits that can occur when calculating a negative value. */
void verinum::signed_trim() {
  /* Do we have any extra digits? */
  unsigned tlen = nbits_ - 1;
  verinum::V sign = bits_[tlen];
  while ((tlen > 0) && (bits_[tlen] == sign)) tlen -= 1;

  /* tlen now points to the first digit that is not the sign.
   * or bit 0. Set the length to include this bit and one proper
   * sign bit if needed. */
  if (bits_[tlen] != sign) tlen += 1;
  tlen += 1;

  /* Trim the bits if needed. */
  if (tlen < nbits_) {
    V* tbits = new V[tlen];
    for (unsigned idx = 0; idx < tlen; idx += 1) tbits[idx] = bits_[idx];
    delete[] bits_;
    bits_ = tbits;
    nbits_ = tlen;
  }
}

verinum::verinum(const verinum& that) {
  string_flag_ = that.string_flag_;
  nbits_ = that.nbits_;
  bits_ = new V[nbits_];
  has_len_ = that.has_len_;
  has_sign_ = that.has_sign_;
  is_single_ = that.is_single_;
  for (unsigned idx = 0; idx < nbits_; idx += 1) bits_[idx] = that.bits_[idx];
}

verinum::verinum(const verinum& that, unsigned nbits) {
  string_flag_ = that.string_flag_ && (that.nbits_ == nbits);
  nbits_ = nbits;
  bits_ = new V[nbits_];
  has_len_ = true;
  has_sign_ = that.has_sign_;
  is_single_ = false;

  unsigned copy = nbits;
  if (copy > that.nbits_) copy = that.nbits_;
  for (unsigned idx = 0; idx < copy; idx += 1) bits_[idx] = that.bits_[idx];

  if (copy < nbits_) {
    if (has_sign_ || that.is_single_) {
      for (unsigned idx = copy; idx < nbits_; idx += 1)
        bits_[idx] = bits_[idx - 1];
    } else {
      for (unsigned idx = copy; idx < nbits_; idx += 1)
        bits_[idx] = verinum::V0;
    }
  }
}

verinum::verinum(int64_t that)
    : has_len_(false), has_sign_(true), is_single_(false), string_flag_(false) {
  int64_t tmp;

  if (that < 0)
    tmp = (that + 1) / 2;
  else
    tmp = that / 2;
  nbits_ = 1;
  while (tmp != 0) {
    nbits_ += 1;
    tmp /= 2;
  }

  nbits_ += 1;

  bits_ = new V[nbits_];
  for (unsigned idx = 0; idx < nbits_; idx += 1) {
    bits_[idx] = (that & 1) ? V1 : V0;
    that >>= 1;
  }
}

verinum::~verinum() { delete[] bits_; }

verinum& verinum::operator=(const verinum& that) {
  if (this == &that) return *this;
  if (nbits_ != that.nbits_) {
    delete[] bits_;
    nbits_ = that.nbits_;
    bits_ = new V[that.nbits_];
  }
  for (unsigned idx = 0; idx < nbits_; idx += 1) bits_[idx] = that.bits_[idx];

  has_len_ = that.has_len_;
  has_sign_ = that.has_sign_;
  is_single_ = that.is_single_;
  string_flag_ = that.string_flag_;
  return *this;
}

verinum::V verinum::get(unsigned idx) const {
  assert(idx < nbits_);
  return bits_[idx];
}

verinum::V verinum::set(unsigned idx, verinum::V val) {
  assert(idx < nbits_);
  return bits_[idx] = val;
}

void verinum::set(unsigned off, const verinum& val) {
  assert(off + val.len() <= nbits_);
  for (unsigned idx = 0; idx < val.len(); idx += 1) bits_[off + idx] = val[idx];
}

unsigned verinum::as_unsigned() const {
  if (nbits_ == 0) return 0;

  if (!is_defined()) return 0;

  unsigned val = 0;
  unsigned mask = 1;
  for (unsigned idx = 0; idx < nbits_; idx += 1, mask <<= 1)
    if (bits_[idx] == V1) {
      if (mask == 0) return ~mask;
      val |= mask;
    }

  return val;
}

unsigned long verinum::as_ulong() const {
  if (nbits_ == 0) return 0;

  if (!is_defined()) return 0;

  unsigned long val = 0;
  unsigned long mask = 1;
  for (unsigned idx = 0; idx < nbits_; idx += 1, mask <<= 1)
    if (bits_[idx] == V1) {
      if (mask == 0) return ~mask;
      val |= mask;
    }

  return val;
}

uint64_t verinum::as_ulong64() const {
  if (nbits_ == 0) return 0;

  if (!is_defined()) return 0;

  uint64_t val = 0;
  uint64_t mask = 1;
  for (unsigned idx = 0; idx < nbits_; idx += 1, mask <<= 1)
    if (bits_[idx] == V1) {
      if (mask == 0) return ~mask;
      val |= mask;
    }

  return val;
}

/*
 * This function returns the native long integer that represents the
 * value of this object. It accounts for sign extension if the value
 * is signed.
 *
 * If the value is undefined, return 0.
 *
 * This function presumes that the native format is 2s complement
 * (pretty safe these days) and masks/sets bits accordingly. If the
 * value is too large for the native form, it truncates the high bits.
 */
signed long verinum::as_long() const {
#define IVLLBITS (8 * sizeof(long) - 1)
  if (nbits_ == 0) return 0;

  if (!is_defined()) return 0;

  signed long val = 0;
  unsigned diag_top = 0;

  unsigned top = nbits_;
  if (top > IVLLBITS) {
    diag_top = top;
    top = IVLLBITS;
  }
  int lost_bits = 0;

  if (has_sign_ && (bits_[nbits_ - 1] == V1)) {
    val = -1;
    signed long mask = ~1L;
    for (unsigned idx = 0; idx < top; idx += 1) {
      if (bits_[idx] == V0) val &= mask;
      mask = (mask << 1) | 1L;
    }
    if (diag_top) {
      for (unsigned idx = top; idx < diag_top; idx += 1) {
        if (bits_[idx] == V0) lost_bits = 1;
      }
    }
  } else {
    signed long mask = 1;
    for (unsigned idx = 0; idx < top; idx += 1, mask <<= 1) {
      if (bits_[idx] == V1) val |= mask;
    }
    if (diag_top) {
      for (unsigned idx = top; idx < diag_top; idx += 1) {
        if (bits_[idx] == V1) lost_bits = 1;
      }
    }
  }

  if (lost_bits)
    cerr << "warning: verinum::as_long() truncated " << diag_top << " bits to "
         << IVLLBITS << ", returns " << val << endl;
  return val;
#undef IVLLBITS
}

double verinum::as_double() const {
  if (nbits_ == 0) return 0.0;

  double val = 0.0;
  /* Do we have/want a signed value? */
  if (has_sign_ && bits_[nbits_ - 1] == V1) {
    V carry = V1;
    for (unsigned idx = 0; idx < nbits_; idx += 1) {
      V sum = add_with_carry(~bits_[idx], V0, carry);
      if (sum == V1) val += pow(2.0, (double)idx);
    }
    val *= -1.0;
  } else {
    for (unsigned idx = 0; idx < nbits_; idx += 1) {
      if (bits_[idx] == V1) val += pow(2.0, (double)idx);
    }
  }
  return val;
}

string verinum::as_string() const {
  assert(nbits_ % 8 == 0);
  if (nbits_ == 0) return "";

  string res;
  for (unsigned idx = nbits_; idx > 0; idx -= 8) {
    char char_val = 0;
    V* bp = bits_ + idx;

    if (*(--bp) == V1) char_val |= 0x80;
    if (*(--bp) == V1) char_val |= 0x40;
    if (*(--bp) == V1) char_val |= 0x20;
    if (*(--bp) == V1) char_val |= 0x10;
    if (*(--bp) == V1) char_val |= 0x08;
    if (*(--bp) == V1) char_val |= 0x04;
    if (*(--bp) == V1) char_val |= 0x02;
    if (*(--bp) == V1) char_val |= 0x01;

    if (char_val == '"' || char_val == '\\') {
      char tmp[5];
      snprintf(tmp, sizeof tmp, "\\%03o", char_val);
      res = res + tmp;
    } else if (isprint(char_val)) {
      res = res + char_val;
    } else {
      char tmp[5];
      snprintf(tmp, sizeof tmp, "\\%03o", (unsigned char)char_val);
      res = res + tmp;
    }
  }
  return res;
}

bool verinum::is_before(const verinum& that) const {
  if (that.nbits_ > nbits_) return true;
  if (that.nbits_ < nbits_) return false;

  for (unsigned idx = nbits_; idx > 0; idx -= 1) {
    if (bits_[idx - 1] < that.bits_[idx - 1]) return true;
    if (bits_[idx - 1] > that.bits_[idx - 1]) return false;
  }
  return false;
}

bool verinum::is_defined() const {
  for (unsigned idx = 0; idx < nbits_; idx += 1) {
    if (bits_[idx] == Vx) return false;
    if (bits_[idx] == Vz) return false;
  }
  return true;
}

bool verinum::is_zero() const {
  for (unsigned idx = 0; idx < nbits_; idx += 1)
    if (bits_[idx] != V0) return false;

  return true;
}

bool verinum::is_negative() const {
  return (bits_[nbits_ - 1] == V1) && has_sign();
}

unsigned verinum::significant_bits() const {
  unsigned sbits = nbits_;

  if (has_sign_) {
    V sign_bit = bits_[sbits - 1];
    while ((sbits > 1) && (bits_[sbits - 2] == sign_bit)) sbits -= 1;
  } else {
    while ((sbits > 1) && (bits_[sbits - 1] == verinum::V0)) sbits -= 1;
  }
  return sbits;
}

void verinum::cast_to_int2() {
  for (unsigned idx = 0; idx < nbits_; idx += 1) {
    if (bits_[idx] == Vx || bits_[idx] == Vz) bits_[idx] = V0;
  }
}

verinum pad_to_width(const verinum& that, unsigned width) {
  if (that.len() >= width) return that;

  if (that.len() == 0) {
    verinum val(verinum::V0, width, that.has_len());
    val.has_sign(that.has_sign());
    return val;
  }

  verinum::V pad = that[that.len() - 1];
  if (pad == verinum::V1 && !that.has_sign() && !that.is_single())
    pad = verinum::V0;
  if (that.has_len() && !that.has_sign() && !that.is_single()) {
    if (pad == verinum::Vx) pad = verinum::V0;
    if (pad == verinum::Vz) pad = verinum::V0;
  }

  verinum val(pad, width, that.has_len());

  for (unsigned idx = 0; idx < that.len(); idx += 1) val.set(idx, that[idx]);

  val.has_sign(that.has_sign());
  if (that.is_string() && (width % 8) == 0) {
    val = verinum(val.as_string());
  }
  return val;
}

verinum cast_to_width(const verinum& that, unsigned width) {
  if (that.has_len() && (that.len() == width)) return that;

  if (that.len() >= width) return verinum(that, width);

  if (that.len() == 0) {
    verinum val(verinum::V0, width, true);
    val.has_sign(that.has_sign());
    return val;
  }

  verinum::V pad = that[that.len() - 1];
  if (pad == verinum::V1 && !that.has_sign() && !that.is_single())
    pad = verinum::V0;
  if (that.has_len() && !that.has_sign() && !that.is_single()) {
    if (pad == verinum::Vx) pad = verinum::V0;
    if (pad == verinum::Vz) pad = verinum::V0;
  }

  verinum val(pad, width, true);

  for (unsigned idx = 0; idx < that.len(); idx += 1) val.set(idx, that[idx]);

  val.has_sign(that.has_sign());
  return val;
}

/*
 * This function returns a version of the verinum that has only as
 * many bits as are needed to accurately represent the value. It takes
 * into account the signedness of the value.
 *
 * If the input value has a definite length, then that value is just
 * returned as is.
 */
verinum trim_vnum(const verinum& that) {
  unsigned tlen;

  if (that.has_len()) return that;

  if (that.len() < 2) return that;

  if (that.has_sign()) {
    unsigned top = that.len() - 1;
    verinum::V sign = that.get(top);

    while ((top > 0) && (that.get(top) == sign)) top -= 1;

    /* top points to the first digit that is not the
       sign. Set the length to include this and one proper
       sign bit. */

    if (that.get(top) != sign) top += 1;

    tlen = top + 1;

  } else {
    /* If the result is unsigned and has an indefinite
       length, then trim off all but one leading zero. */
    unsigned top = that.len() - 1;
    while ((top > 0) && (that.get(top) == verinum::V0)) top -= 1;

    /* Now top is the index of the highest non-zero bit. If
       that turns out to the highest bit in the vector, then
       there is no trimming possible. */
    if (top + 1 == that.len()) return that;

    /* Make tlen wide enough to include the highest non-zero
       bit, plus one extra 0 bit. */
    tlen = top + 2;

    /* This can only happen when the verinum is all zeros,
       so make it a single bit wide. */
    if (that.get(top) == verinum::V0) tlen -= 1;
  }

  verinum tmp(verinum::V0, tlen, false);
  tmp.has_sign(that.has_sign());
  for (unsigned idx = 0; idx < tmp.len(); idx += 1) tmp.set(idx, that.get(idx));

  return tmp;
}

ostream& operator<<(ostream& o, verinum::V v) {
  switch (v) {
    case verinum::V0:
      o << "0";
      break;
    case verinum::V1:
      o << "1";
      break;
    case verinum::Vx:
      o << "x";
      break;
    case verinum::Vz:
      o << "z";
      break;
  }
  return o;
}

/*
 * This operator is used by various dumpers to write the Verilog
 * number in a Verilog format.
 */
ostream& operator<<(ostream& o, const verinum& v) {
  if (v.is_string()) {
    o << "\"" << v.as_string() << "\"";
    return o;
  }

  /* If the verinum number has a fixed length, dump all the bits
     literally. This is how we express the fixed length in the
     output. */
  if (v.has_len()) {
    o << v.len();
  }

  /* If the number is fully defined (no x or z) then print it
     out as a decimal number. */
  unsigned dec_len = 8 * sizeof(int); /* avoid 32/64 bit differences. */
  if (!v.has_sign()) dec_len -= 1;    /* an unsigned number. */
  if (v.is_defined() && v.len() <= dec_len) {
    if (v.has_sign())
      o << "'sd" << v.as_long();
    else
      o << "'d" << v.as_ulong();
    return o;
  }

  /* Oh, well. Print the minimum to get the value properly
     displayed. */
  if (v.has_sign())
    o << "'sb";
  else
    o << "'b";

  if (v.len() == 0) {
    o << "0";
    return o;
  }

  verinum::V trim_left = v.get(v.len() - 1);
  unsigned idx;

  if (v.has_sign()) {
    for (idx = v.len() - 1; idx > 0; idx -= 1)
      if (trim_left != v.get(idx - 1)) break;

    o << trim_left;
  } else {
    idx = v.len();
  }

  while (idx > 0) {
    o << v.get(idx - 1);
    idx -= 1;
  }

  return o;
}

verinum::V operator==(const verinum& left, const verinum& right) {
  verinum::V left_pad = verinum::V0;
  verinum::V right_pad = verinum::V0;
  if (left.has_sign() && right.has_sign()) {
    left_pad = left.get(left.len() - 1);
    right_pad = right.get(right.len() - 1);

    if (left_pad == verinum::V1 && right_pad == verinum::V0) return verinum::V0;
    if (left_pad == verinum::V0 && right_pad == verinum::V1) return verinum::V0;
  }

  unsigned max_len = left.len();
  if (right.len() > max_len) max_len = right.len();

  for (unsigned idx = 0; idx < max_len; idx += 1) {
    verinum::V left_bit = idx < left.len() ? left[idx] : left_pad;
    verinum::V right_bit = idx < right.len() ? right[idx] : right_pad;
    if (left_bit != right_bit) return verinum::V0;
  }

  return verinum::V1;
}

verinum::V operator<=(const verinum& left, const verinum& right) {
  verinum::V left_pad = verinum::V0;
  verinum::V right_pad = verinum::V0;
  bool signed_calc = left.has_sign() && right.has_sign();
  if (signed_calc) {
    left_pad = left.get(left.len() - 1);
    right_pad = right.get(right.len() - 1);

    if (left_pad == verinum::V1 && right_pad == verinum::V0) return verinum::V1;
    if (left_pad == verinum::V0 && right_pad == verinum::V1) return verinum::V0;
  }

  unsigned idx;
  for (idx = left.len(); idx > right.len(); idx -= 1) {
    if (left[idx - 1] != right_pad) {
      // A change of padding for a negative left argument
      // denotes the left value is less than the right.
      return (signed_calc && (left_pad == verinum::V1)) ? verinum::V1
                                                        : verinum::V0;
    }
  }

  for (idx = right.len(); idx > left.len(); idx -= 1) {
    if (right[idx - 1] != left_pad) {
      // A change of padding for a negative right argument
      // denotes the left value is not less than the right.
      return (signed_calc && (right_pad == verinum::V1)) ? verinum::V0
                                                         : verinum::V1;
    }
  }

  idx = right.len();
  if (left.len() < idx) idx = left.len();

  while (idx > 0) {
    if (left[idx - 1] == verinum::Vx) return verinum::Vx;
    if (left[idx - 1] == verinum::Vz) return verinum::Vx;
    if (right[idx - 1] == verinum::Vx) return verinum::Vx;
    if (right[idx - 1] == verinum::Vz) return verinum::Vx;
    if (left[idx - 1] > right[idx - 1]) return verinum::V0;
    if (left[idx - 1] < right[idx - 1]) return verinum::V1;
    idx -= 1;
  }

  return verinum::V1;
}

verinum::V operator<(const verinum& left, const verinum& right) {
  verinum::V left_pad = verinum::V0;
  verinum::V right_pad = verinum::V0;
  bool signed_calc = left.has_sign() && right.has_sign();
  if (signed_calc) {
    left_pad = left.get(left.len() - 1);
    right_pad = right.get(right.len() - 1);

    if (left_pad == verinum::V1 && right_pad == verinum::V0) return verinum::V1;
    if (left_pad == verinum::V0 && right_pad == verinum::V1) return verinum::V0;
  }

  unsigned idx;
  for (idx = left.len(); idx > right.len(); idx -= 1) {
    if (left[idx - 1] != right_pad) {
      // A change of padding for a negative left argument
      // denotes the left value is less than the right.
      return (signed_calc && (left_pad == verinum::V1)) ? verinum::V1
                                                        : verinum::V0;
    }
  }

  for (idx = right.len(); idx > left.len(); idx -= 1) {
    if (right[idx - 1] != left_pad) {
      // A change of padding for a negative right argument
      // denotes the left value is not less than the right.
      return (signed_calc && (right_pad == verinum::V1)) ? verinum::V0
                                                         : verinum::V1;
    }
  }

  while (idx > 0) {
    if (left[idx - 1] == verinum::Vx) return verinum::Vx;
    if (left[idx - 1] == verinum::Vz) return verinum::Vx;
    if (right[idx - 1] == verinum::Vx) return verinum::Vx;
    if (right[idx - 1] == verinum::Vz) return verinum::Vx;
    if (left[idx - 1] > right[idx - 1]) return verinum::V0;
    if (left[idx - 1] < right[idx - 1]) return verinum::V1;
    idx -= 1;
  }

  return verinum::V0;
}

static verinum::V add_with_carry(verinum::V l, verinum::V r, verinum::V& c) {
  unsigned sum = 0;
  switch (c) {
    case verinum::Vx:
    case verinum::Vz:
      c = verinum::Vx;
      return verinum::Vx;
    case verinum::V0:
      break;
    case verinum::V1:
      sum += 1;
  }

  switch (l) {
    case verinum::Vx:
    case verinum::Vz:
      c = verinum::Vx;
      return verinum::Vx;
    case verinum::V0:
      break;
    case verinum::V1:
      sum += 1;
      break;
  }

  switch (r) {
    case verinum::Vx:
    case verinum::Vz:
      c = verinum::Vx;
      return verinum::Vx;
    case verinum::V0:
      break;
    case verinum::V1:
      sum += 1;
      break;
  }

  if (sum & 2)
    c = verinum::V1;
  else
    c = verinum::V0;
  if (sum & 1)
    return verinum::V1;
  else
    return verinum::V0;
}

verinum operator~(const verinum& left) {
  verinum val = left;
  for (unsigned idx = 0; idx < val.len(); idx += 1) switch (val[idx]) {
      case verinum::V0:
        val.set(idx, verinum::V1);
        break;
      case verinum::V1:
        val.set(idx, verinum::V0);
        break;
      default:
        val.set(idx, verinum::Vx);
        break;
    }

  return val;
}

/*
 * Addition and subtraction works a bit at a time, from the least
 * significant up to the most significant. The result is signed only
 * if both of the operands are signed. If either operand is unsized,
 * the result is expanded as needed to prevent overflow.
 */

verinum operator+(const verinum& left, const verinum& right) {
  const bool has_len_flag = left.has_len() && right.has_len();
  const bool signed_flag = left.has_sign() && right.has_sign();

  unsigned min_len = min(left.len(), right.len());
  unsigned max_len = max(left.len(), right.len());

  // If either the left or right values are undefined, the
  // entire result is undefined.
  if (!left.is_defined() || !right.is_defined()) {
    unsigned len = has_len_flag ? max_len : 1;
    verinum result(verinum::Vx, len, has_len_flag);
    result.has_sign(signed_flag);
    return result;
  }

  verinum::V* val_bits = new verinum::V[max_len + 1];

  verinum::V carry = verinum::V0;
  for (unsigned idx = 0; idx < min_len; idx += 1)
    val_bits[idx] = add_with_carry(left[idx], right[idx], carry);

  verinum::V rpad = sign_bit(right);
  verinum::V lpad = sign_bit(left);

  if (left.len() > right.len()) {
    for (unsigned idx = min_len; idx < max_len; idx += 1)
      val_bits[idx] = add_with_carry(left[idx], rpad, carry);

  } else {
    for (unsigned idx = min_len; idx < max_len; idx += 1)
      val_bits[idx] = add_with_carry(lpad, right[idx], carry);
  }

  unsigned len = max_len;
  if (!has_len_flag) {
    val_bits[max_len] = add_with_carry(lpad, rpad, carry);
    if (signed_flag) {
      if (val_bits[max_len] != val_bits[max_len - 1]) len += 1;
    } else {
      if (val_bits[max_len] != verinum::V0) len += 1;
    }
  }
  verinum result(val_bits, len, has_len_flag);
  result.has_sign(signed_flag);

  delete[] val_bits;

  return result;
}

verinum operator-(const verinum& left, const verinum& right) {
  const bool has_len_flag = left.has_len() && right.has_len();
  const bool signed_flag = left.has_sign() && right.has_sign();

  unsigned min_len = min(left.len(), right.len());
  unsigned max_len = max(left.len(), right.len());

  // If either the left or right values are undefined, the
  // entire result is undefined.
  if (!left.is_defined() || !right.is_defined()) {
    unsigned len = has_len_flag ? max_len : 1;
    verinum result(verinum::Vx, len, has_len_flag);
    result.has_sign(signed_flag);
    return result;
  }

  verinum::V* val_bits = new verinum::V[max_len + 1];

  verinum::V carry = verinum::V1;
  for (unsigned idx = 0; idx < min_len; idx += 1)
    val_bits[idx] = add_with_carry(left[idx], ~right[idx], carry);

  verinum::V rpad = sign_bit(right);
  verinum::V lpad = sign_bit(left);

  if (left.len() > right.len()) {
    for (unsigned idx = min_len; idx < max_len; idx += 1)
      val_bits[idx] = add_with_carry(left[idx], ~rpad, carry);

  } else {
    for (unsigned idx = min_len; idx < max_len; idx += 1)
      val_bits[idx] = add_with_carry(lpad, ~right[idx], carry);
  }

  unsigned len = max_len;
  if (signed_flag && !has_len_flag) {
    val_bits[max_len] = add_with_carry(lpad, ~rpad, carry);
    if (val_bits[max_len] != val_bits[max_len - 1]) len += 1;
  }
  verinum result(val_bits, len, has_len_flag);
  result.has_sign(signed_flag);

  delete[] val_bits;

  return result;
}

verinum operator-(const verinum& right) {
  const bool has_len_flag = right.has_len();
  const bool signed_flag = right.has_sign();

  unsigned len = right.len();

  // If either the left or right values are undefined, the
  // entire result is undefined.
  if (!right.is_defined()) {
    verinum result(verinum::Vx, has_len_flag ? len : 1, has_len_flag);
    result.has_sign(signed_flag);
    return result;
  }

  verinum::V* val_bits = new verinum::V[len + 1];

  verinum::V carry = verinum::V1;
  for (unsigned idx = 0; idx < len; idx += 1)
    val_bits[idx] = add_with_carry(verinum::V0, ~right[idx], carry);

  if (signed_flag && !has_len_flag) {
    val_bits[len] = add_with_carry(verinum::V0, ~sign_bit(right), carry);
    if (val_bits[len] != val_bits[len - 1]) len += 1;
  }
  verinum result(val_bits, len, has_len_flag);
  result.has_sign(signed_flag);

  delete[] val_bits;

  return result;
}

/*
 * This operator multiplies the left number by the right number. The
 * result is signed only if both of the operands are signed. If either
 * operand is unsized, the resulting number is as large as the sum of
 * the sizes of the operands.
 *
 * The algorithm used is successive shift and add operations,
 * implemented as the nested loops.
 */
verinum operator*(const verinum& left, const verinum& right) {
  const bool has_len_flag = left.has_len() && right.has_len();
  const bool signed_flag = left.has_sign() && right.has_sign();

  const unsigned l_len = left.len();
  const unsigned r_len = right.len();

  unsigned len = has_len_flag ? max(l_len, r_len) : l_len + r_len;

  // If either the left or right values are undefined, the
  // entire result is undefined.
  if (!left.is_defined() || !right.is_defined()) {
    verinum result(verinum::Vx, has_len_flag ? len : 1, has_len_flag);
    result.has_sign(signed_flag);
    return result;
  }

  verinum result(verinum::V0, len, has_len_flag);
  result.has_sign(signed_flag);

  verinum::V r_sign = sign_bit(right);
  for (unsigned rdx = 0; rdx < len; rdx += 1) {
    verinum::V r_bit = rdx < r_len ? right.get(rdx) : r_sign;
    if (r_bit == verinum::V0) continue;

    verinum::V l_sign = sign_bit(left);
    verinum::V carry = verinum::V0;
    for (unsigned ldx = 0; ldx < (len - rdx); ldx += 1) {
      verinum::V l_bit = ldx < l_len ? left[ldx] : l_sign;
      result.set(ldx + rdx, add_with_carry(l_bit, result[rdx + ldx], carry));
    }
  }

  return trim_vnum(result);
}

static verinum make_p_one(unsigned len, bool has_len, bool has_sign) {
  verinum tmp(verinum::V0, has_len ? len : 2, has_len);
  tmp.set(0, verinum::V1);
  tmp.has_sign(has_sign);
  return tmp;
}

static verinum make_m_one(unsigned len, bool has_len, bool has_sign) {
  verinum tmp(verinum::V1, has_len ? len : 1, has_len);
  tmp.has_sign(has_sign);
  return tmp;
}

static verinum recursive_pow(const verinum& left, verinum& right) {
  // If the exponent is zero, return a value of 1
  if (right.is_zero()) {
    return make_p_one(left.len(), left.has_len(), left.has_sign());
  }

  verinum result;
  if (right.get(0) == 1) {
    // The exponent is odd, so subtract 1 from it and recurse.
    // We know it's odd, so the subtraction is easy.
    right.set(0, verinum::V0);
    result = pow(left, right);
    result = left * result;
  } else {
    // The exponent is even, so divide it by 2 and recurse
    right = right >> 1;
    result = pow(left, right);
    result = result * result;
  }
  return result;
}

verinum pow(const verinum& left, const verinum& right) {
  verinum result;

  // We need positive and negative one in a few places.
  verinum p_one = make_p_one(left.len(), left.has_len(), left.has_sign());
  verinum m_one = make_m_one(left.len(), left.has_len(), left.has_sign());

  // If either the left or right values are undefined, the
  // entire result is undefined.
  if (!left.is_defined() || !right.is_defined()) {
    result = verinum(verinum::Vx, left.len(), left.has_len());
    result.has_sign(left.has_sign());

    // If the right value is zero we need to set the result to 1.
  } else if (right.is_zero()) {
    result = p_one;

  } else if (right.is_negative()) {
    // 0 ** <negative> is 'bx.
    if (left.is_zero()) {
      result = verinum(verinum::Vx, left.len(), left.has_len());
      result.has_sign(left.has_sign());

      // -1 ** <negative> is 1 or -1. Note that this must be done
      // before testing for +1 in case 'left' has a width of 1.
    } else if (left.has_sign() && left == m_one) {
      if (right.get(0) == verinum::V0) {
        result = p_one;
      } else {
        result = m_one;
      }

      // 1 ** <negative> is 1.
    } else if (left == p_one) {
      result = p_one;

      // Everything else is 0.
    } else {
      result = verinum(verinum::V0, left.len(), left.has_len());
      result.has_sign(left.has_sign());
    }

  } else {
    verinum exponent = right;
    result = recursive_pow(left, exponent);
  }

  return trim_vnum(result);
}

verinum operator<<(const verinum& that, unsigned shift) {
  bool has_len_flag = that.has_len();

  unsigned len = that.len();
  if (!has_len_flag) len += shift;

  verinum result(verinum::V0, len, has_len_flag);
  result.has_sign(that.has_sign());

  for (unsigned idx = shift; idx < len; idx += 1)
    result.set(idx, that.get(idx - shift));

  return trim_vnum(result);
}

verinum operator>>(const verinum& that, unsigned shift) {
  bool has_len_flag = that.has_len();

  unsigned len = that.len();

  verinum::V sign_bit = that.has_sign() ? that.get(len - 1) : verinum::V0;

  if (shift >= len) {
    if (!has_len_flag) len = 1;
    verinum result(sign_bit, len, has_len_flag);
    result.has_sign(that.has_sign());
    return result;
  }

  if (!has_len_flag) len -= shift;
  verinum result(sign_bit, len, has_len_flag);
  result.has_sign(that.has_sign());

  for (unsigned idx = shift; idx < that.len(); idx += 1)
    result.set(idx - shift, that.get(idx));

  return trim_vnum(result);
}

static verinum unsigned_divide(verinum num, verinum den, bool signed_result) {
  // We need the following calculations to be lossless. The
  // result will be cast to the required width by the caller.
  num.has_len(false);
  den.has_len(false);

  unsigned nwid = num.len();
  while (nwid > 0 && (num.get(nwid - 1) == verinum::V0)) nwid -= 1;

  unsigned dwid = den.len();
  while (dwid > 0 && (den.get(dwid - 1) == verinum::V0)) dwid -= 1;

  if (dwid > nwid) return verinum(verinum::V0, 1);

  den = den << (nwid - dwid);

  unsigned idx = nwid - dwid + 1;
  verinum result(verinum::V0, signed_result ? idx + 1 : idx);
  if (signed_result) {
    result.set(idx, verinum::V0);
    result.has_sign(true);
  }
  while (idx > 0) {
    if (den <= num) {
      verinum dif = num - den;
      num = dif;
      result.set(idx - 1, verinum::V1);
    }
    den = den >> 1;
    idx -= 1;
  }

  return result;
}

static verinum unsigned_modulus(verinum num, verinum den) {
  // We need the following calculations to be lossless. The
  // result will be cast to the required width by the caller.
  num.has_len(false);
  den.has_len(false);

  unsigned nwid = num.len();
  while (nwid > 0 && (num.get(nwid - 1) == verinum::V0)) nwid -= 1;

  unsigned dwid = den.len();
  while (dwid > 0 && (den.get(dwid - 1) == verinum::V0)) dwid -= 1;

  if (dwid > nwid) return num;

  den = den << (nwid - dwid);

  unsigned idx = nwid - dwid + 1;
  while (idx > 0) {
    if (den <= num) {
      verinum dif = num - den;
      num = dif;
    }
    den = den >> 1;
    idx -= 1;
  }

  return num;
}

/*
 * This operator divides the left number by the right number. The result
 * is signed only if both of the operands are signed.
 */
verinum operator/(const verinum& left, const verinum& right) {
  const bool has_len_flag = left.has_len() && right.has_len();
  const bool signed_flag = left.has_sign() && right.has_sign();

  unsigned use_len = left.len();

  // If either the left or right values are undefined, or the
  // right value is zero, the entire result is undefined.
  if (!left.is_defined() || !right.is_defined() || right.is_zero()) {
    verinum result(verinum::Vx, use_len, has_len_flag);
    result.has_sign(signed_flag);
    return result;
  }

  verinum result(verinum::Vz, use_len, has_len_flag);

  /* do the operation differently, depending on whether the
     result is signed or not. */
  if (signed_flag) {
    if (use_len <= (8 * sizeof(long) - 1)) {
      long l = left.as_long();
      long r = right.as_long();
      bool overflow = (l == LONG_MIN) && (r == -1);
      long v = overflow ? LONG_MIN : l / r;
      for (unsigned idx = 0; idx < use_len; idx += 1) {
        result.set(idx, (v & 1) ? verinum::V1 : verinum::V0);
        v >>= 1;
      }

    } else {
      verinum use_left, use_right;
      bool negative = false;
      if (left.is_negative()) {
        use_left = -left;
        negative = !negative;
      } else {
        use_left = left;
      }
      use_left.has_sign(false);
      if (right.is_negative()) {
        use_right = -right;
        negative = !negative;
      } else {
        use_right = right;
      }
      use_right.has_sign(false);
      result = unsigned_divide(use_left, use_right, true);
      if (negative) result = -result;
    }

  } else {
    if (use_len <= 8 * sizeof(unsigned long)) {
      /* Use native unsigned division to do the work. */

      unsigned long l = left.as_ulong();
      unsigned long r = right.as_ulong();
      unsigned long v = l / r;
      for (unsigned idx = 0; idx < use_len; idx += 1) {
        result.set(idx, (v & 1) ? verinum::V1 : verinum::V0);
        v >>= 1;
      }

    } else {
      result = unsigned_divide(left, right, false);
    }
  }

  if (has_len_flag) result = cast_to_width(result, use_len);

  result.has_sign(signed_flag);
  return trim_vnum(result);
}

verinum operator%(const verinum& left, const verinum& right) {
  const bool has_len_flag = left.has_len() && right.has_len();
  const bool signed_flag = left.has_sign() && right.has_sign();

  unsigned use_len = left.len();

  // If either the left or right values are undefined, or the
  // right value is zero, the entire result is undefined.
  if (!left.is_defined() || !right.is_defined() || right.is_zero()) {
    verinum result(verinum::Vx, use_len, has_len_flag);
    result.has_sign(signed_flag);
    return result;
  }

  verinum result(verinum::Vz, use_len, has_len_flag);

  if (signed_flag) {
    if (use_len <= 8 * sizeof(long)) {
      /* Use native signed modulus to do the work. */
      long l = left.as_long();
      long r = right.as_long();
      bool overflow = (l == LONG_MIN) && (r == -1);
      long v = overflow ? 0 : l % r;
      for (unsigned idx = 0; idx < use_len; idx += 1) {
        result.set(idx, (v & 1) ? verinum::V1 : verinum::V0);
        v >>= 1;
      }
    } else {
      verinum use_left, use_right;
      bool negative = false;
      if (left.is_negative()) {
        use_left = -left;
        negative = true;
      } else {
        use_left = left;
      }
      use_left.has_sign(false);
      if (right.is_negative()) {
        use_right = -right;
      } else {
        use_right = right;
      }
      use_right.has_sign(false);
      result = unsigned_modulus(use_left, use_right);
      if (negative) result = -result;
    }
  } else {
    if (use_len <= 8 * sizeof(unsigned long)) {
      /* Use native unsigned modulus to do the work. */
      unsigned long l = left.as_ulong();
      unsigned long r = right.as_ulong();
      unsigned long v = l % r;
      for (unsigned idx = 0; idx < use_len; idx += 1) {
        result.set(idx, (v & 1) ? verinum::V1 : verinum::V0);
        v >>= 1;
      }
    } else {
      result = unsigned_modulus(left, right);
    }
  }

  if (has_len_flag) result = cast_to_width(result, use_len);

  result.has_sign(signed_flag);
  return trim_vnum(result);
}

verinum concat(const verinum& left, const verinum& right) {
  if (left.is_string() && right.is_string()) {
    std::string tmp = left.as_string() + right.as_string();
    verinum res(tmp);
    return res;
  }

  verinum res(verinum::V0, left.len() + right.len());
  for (unsigned idx = 0; idx < right.len(); idx += 1)
    res.set(idx, right.get(idx));

  for (unsigned idx = 0; idx < left.len(); idx += 1)
    res.set(idx + right.len(), left.get(idx));

  return res;
}

verinum::V operator~(verinum::V l) {
  switch (l) {
    case verinum::V0:
      return verinum::V1;
    case verinum::V1:
      return verinum::V0;
    default:
      return verinum::Vx;
  }
}

verinum::V operator|(verinum::V l, verinum::V r) {
  if (l == verinum::V1) return verinum::V1;
  if (r == verinum::V1) return verinum::V1;
  if (l != verinum::V0) return verinum::Vx;
  if (r != verinum::V0) return verinum::Vx;
  return verinum::V0;
}

verinum::V operator&(verinum::V l, verinum::V r) {
  if (l == verinum::V0) return verinum::V0;
  if (r == verinum::V0) return verinum::V0;
  if (l != verinum::V1) return verinum::Vx;
  if (r != verinum::V1) return verinum::Vx;
  return verinum::V1;
}

verinum::V operator^(verinum::V l, verinum::V r) {
  if (l == verinum::V0) return bit4_z2x(r);
  if (r == verinum::V0) return bit4_z2x(l);
  if ((l == verinum::V1) && (r == verinum::V1)) return verinum::V0;

  return verinum::Vx;
}
